package com.sh.linkedList;

import java.util.Stack;

/**
 * @ClassName SingleLinkedList
 * @Description TODO
 * @Author yaoqiang
 * @Date 2020/10/28 9:51
 * @Version 1.0
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建几个节点
        Node node1 = new Node(1,"aa");
        Node node2 = new Node(2,"bb");
        Node node3 = new Node(3,"cc");
        Node node4 = new Node(4,"dd");
        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(node2);
        singleLinkedList.add(node1);
        singleLinkedList.add(node4);
        singleLinkedList.add(node3);
        singleLinkedList.list();

//        //获取singleLinkedList有效节点数
//        System.out.println(getNodeCount(singleLinkedList.getHead()));
//        System.out.println(getLastIndexNode(singleLinkedList.getHead(),1));

        //测试单链表的反转
        reverseList(singleLinkedList.getHead());
        singleLinkedList.list();

        reverseByStack(singleLinkedList.getHead());
//        //按顺序添加
//        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
//        singleLinkedList2.addByOrder(node2);
//        singleLinkedList2.addByOrder(node1);
//        singleLinkedList2.addByOrder(node4);
//        singleLinkedList2.addByOrder(node2);
//        singleLinkedList2.addByOrder(node3);
//        singleLinkedList2.list();
//        //修改
//        Node node33 = new Node(3, "c");
//        singleLinkedList2.edit(node33);
//        singleLinkedList2.list();
//        //删除节点
//        singleLinkedList2.delete(node1);
//        singleLinkedList2.delete(node4);
//        singleLinkedList2.delete(node2);
//        singleLinkedList2.delete(node3);
//
//        singleLinkedList2.list();







    }

    public static void  reverseByStack(Node head){
        if (head.next==null || head.next.next==null){
            return;
        }
        Node cur=head.next;
        Stack<Node> stack=new Stack<>();
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
        Stack<String> stackTest=new Stack<>();stackTest.add("a");stackTest.add("b");stackTest.add("c");
        while (stack.size()>0){
            System.out.println(stackTest.pop());
        }
    }

    /**
     * 将单链表进行反转
     * 循环，先把cur的next放到next节点上去，
     * 把之前取的res的next给当前cur节点的next(相当于完成反转)
     * 然后把整个cur给res的next，这样是为了把反转后的所有数据挂在res上当做一个整体
     * 把next上的剩余存的给到cur
     */
    public static void reverseList(Node head) {
        //如果链表为空，或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //先定义一个辅助变量，帮助我们遍历原来的变量
        Node cur = head.next;
        Node next = null;//指向当前节点的下一个节点
        Node reverseHead = new Node(0, "");
        while (cur != null) {
            //遍历原来的节点，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
            next = cur.next;//先暂时保存当前节点的下一个节点
            cur.next = reverseHead.next;//将cur的下一个叫节点指向新的链表最前端
            reverseHead.next = cur;//将currnt连接到新的链表上
            cur = next;
        }
        //将head.next指向reverseHead.next实现单链表的反转
        head.next = reverseHead.next;
    }



    //带头结点需要去掉头节点的数量
    public static   int getNodeCount(Node head){
        if (head.next==null){ System.out.println(0);return 0; }
        int count=0;
        Node current=head.next;
        while (current!=null){ count++;current=current.next; }
        return count;
    }

    //查找单链表中的倒数第K个节点
    /**
     * 1、编写一个方法，接收head节点，同时接收一个index
     * 2、index是倒数第index个节点的个数
     * 3、先把链表从头到尾执行，获取到链表的总长度length
     * 3、得到size后，得到size-index个
     * 如果找到返回该节点，否则返回空
     */
    public  static Node getLastIndexNode(Node head,int index){
        if (head==null){
            return null;
        }
        //第一次遍历得到链表的个数
        int size=getNodeCount(head);
        //第二次遍历size-index就是我们倒数的第k个节点
        //先做一个index校验
        if(index<=0||index>size){
            return null;
        }
        //定义辅助变量，循环定位到index
        Node current=head.next;
        for (int i=0;i<size-index;i++){
            current=current.next;
        }
        return current;
    }


}

//定一个SingleLinkedList
class SingleLinkedList {
    //先初始化一个头节点
    private  Node head = new Node(0, "");
    public  Node getHead(){
        return  head;
    }



    //添加节点到单向列表

    /**
     * 当不考虑编号的顺序时，找到当前的链表的最后节点，将最后节点的next域指向新的节点
     *
     * @param node
     */
    public void add(Node node) {
        //因为head的节点不能动，需要一个一个辅助变量
        Node temp = head;
        //遍历链表，找到最后,当退出while循环是，temp指向了链表的最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 考虑编号的顺序时，
     *
     * @param node
     */
    public void addByOrder(Node node) {
        //因为head的节点不能动，需要一个一个辅助变量
        Node temp = head;
        boolean flag = false;//添加的编号是否存在，默认为false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == true) {
            System.out.println("编号存在");
        } else {
            node.next = temp.next;
            temp.next = node;
        }

    }

    //根据编号来修改，即编号不能修改//根据
    public void edit(Node node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = node.name;
        } else {
            System.out.println("不存在");
        }
    }

    public void delete(Node node) {
        Node temp = head;
        boolean flag = false;
        while (true) {
            if (temp == null) {//已经到链表的最后
                break;
            }
            //头结点删除
            if (temp.next.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到");
        }

    }

    public void list() {
        //先判断链表为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //通过辅助变量来遍历
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //出书节点信息
            System.out.println(temp);
            temp = temp.next;
        }

    }

}

//定义一个Node,每个node表示一个节点

class Node {
    public int no;
    public String name;
    public Node next;//指向下一个节点

    //构造器
    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
